package 数据结构与算法.查找算法;

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,1000,1234};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 45));

//        List<Integer> list = binarySearch2(arr, 0, arr.length - 1, 10);
//        System.out.println(list);
    }

    //二分查找
    public static int binarySearch(int[] arr,int left,int right,int findVal){
        System.out.println("查找次数");
        if (left>right){
            return -1;
        }
        int mid=(left+right)/2;
        if (findVal>arr[mid]){
            return binarySearch(arr,mid+1,right,findVal);
        }else if (findVal<arr[mid]){
            return binarySearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }
    }

    //查询相同值的所有元素
    /**
     * 1、找到mid索引值后，向两边扫描，将所有满足的元素下标加入到集合中
     * 2、将集合返回
     */
    public static ArrayList<Integer> binarySearch2(int[] arr,int left,int right,int findVal){

        if (left>right){
            return new ArrayList<Integer>();
        }
        int mid=(left+right)/2;
        if (findVal>arr[mid]){
            return binarySearch2(arr,mid+1,right,findVal);
        }else if (findVal<arr[mid]){
            return binarySearch2(arr,left,mid-1,findVal);
        }else{
            ArrayList<Integer> resIndexList = new ArrayList<>();
            int temp=mid-1;
            while(true){
                if (temp<0||arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp);
                temp-=1;
            }
            resIndexList.add(mid);
            temp=mid+1;
            while(true){
                if (temp>arr.length-1||arr[temp]!=findVal){
                    break;
                }
                resIndexList.add(temp);
                temp+=1;
            }
            return resIndexList;
        }
    }

}
